package com.gxc.integer;

/**
 * 38. 外观数列
 * 「外观数列」是一个数位字符串序列，由递归公式定义：
 *
 * countAndSay(1) = "1"
 * countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。
 *
 * 行程长度编码（RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行长度）和字符的串联。例如，要压缩字符串 "3322251" ，我们将 "33" 用 "23" 替换，将 "222" 用 "32" 替换，将 "5" 用 "15" 替换并将 "1" 用 "11" 替换。因此压缩后字符串变为 "23321511"。
 *
 * 给定一个整数 n ，返回 外观数列 的第 n 个元素
 */
public class CountAndSay {

    public static void main(String[] args) {
        System.out.println(handle(4));
    }

    public static String handle(int n) {
        String res = "1";
        for (int i = 1; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            int slow = 0;
            int fast = 0;
            while (fast<res.length()) {
                if (res.charAt(slow) == res.charAt(fast)) {
                    fast++;
                } else {
                    sb.append(Integer.toString(fast - slow ));
                    sb.append(res.charAt(slow));
                    slow = fast;
                }
            }
            sb.append(Integer.toString(fast - slow ));
            sb.append(res.charAt(slow));
            res = sb.toString();
        }
        return res;
    }

    class Solution {
        public String countAndSay(int n) {
            String str = "1";
            for (int i = 2; i <= n; ++i) {
                StringBuilder sb = new StringBuilder();
                int start = 0;
                int pos = 0;

                while (pos < str.length()) {
                    while (pos < str.length() && str.charAt(pos) == str.charAt(start)) {
                        pos++;
                    }
                    sb.append(Integer.toString(pos - start)).append(str.charAt(start));
                    start = pos;
                }
                str = sb.toString();
            }

            return str;
        }
    }

}
